﻿#include "stdafx.h"
#include "SortLinkLists.h"

using namespace std;

namespace algorithm {
ListNode* CSortLinkLists::Sort(ListNode* head)
{
    // 计算节点数量
    int count = 0;
    ListNode* pNode = head;
    while (pNode) {
        count++;
        pNode = pNode->next;
    }
    // 使用分治法递归排序链表
    return MergeSortedLinkedList(head, count, nullptr, 0);
}
ListNode* CSortLinkLists::MergeSortedLinkedList(ListNode* left, int left_count, ListNode* right, int right_count)
{
    if (left_count > 1)
    {
        // 左节点树大于1，先将左节点继续递归分治排序
        int left_count_new = left_count / 2;
        int right_count = left_count - left_count_new;
        ListNode* pNodeRight = left;
        for (int i = 0; i < left_count_new; i++, pNodeRight = pNodeRight->next);
        left = MergeSortedLinkedList(left, left_count_new, pNodeRight, right_count);
    }
    if (right_count > 1)
    {
        // 右节点树大于1，先将右节点继续递归分治排序
        int left_count = right_count / 2;
        int right_count_new = right_count - left_count;
        ListNode* pNodeRight = right;
        for (int i = 0; i < left_count; i++, pNodeRight = pNodeRight->next);
        right = MergeSortedLinkedList(right, left_count, pNodeRight, right_count_new);
    }

    if (left && right) {
        // 临时头节点，避免需要头节点判空
        ListNode head;
        ListNode* pNode = &head;
        // 左右节点都不为空，则开始合并有序的左右链表节点
        while (left || right) {
            ListNode** ppOpNode = nullptr;
            int* ppOpCount = nullptr;
            do {
                if ((left && !right)) {
                    // 只剩左节点需要合并
                    ppOpNode = &left;
                    ppOpCount = &left_count;
                    break;
                }
                if (right && !left) {
                    // 只剩右节点需要合并
                    ppOpNode = &right;
                    ppOpCount = &right_count;
                    break;
                }
                if (left->val <= right->val) {
                    // 左节点值更小，选择左节点
                    ppOpNode = &left;
                    ppOpCount = &left_count;
                    break;
                }

                // 右节点值更小，选择右节点
                ppOpNode = &right;
                ppOpCount = &right_count;
            } while (0);

            // 存储节点
            pNode->next = *ppOpNode;
            pNode = pNode->next;
            // 节点数减1
            (*ppOpCount)--;
            // 如果节点数为0，则将下一个节点置空。这里主要是因为分割链表操作仅对长度进行分割，
            // 因此尾节点next指针可能不为空
            if (!(*ppOpCount)) {
                (*ppOpNode)->next = nullptr;
            }
            // 继续判断下一个节点
            (*ppOpNode) = (*ppOpNode)->next;
        }
        return head.next;
    }
    else if (left) {
        // 仅左节点不为空，直接返回
        return left;
    }
    else if (right) {
        // 仅右节点不为空，直接返回
        return right;
    }
    else {
        // 左右节点都为空，返回空
        return nullptr;
    }
}
}
